/**
 * 208. 实现 Trie (前缀树)
 * https://leetcode-cn.com/problems/implement-trie-prefix-tree/
 */
public class Solutions_208 {
    public static void main(String[] args) {
        Trie trie = new Trie();

        trie.insert("apple");
        boolean res1 = trie.search("apple");  // output: true
        System.out.println(res1);
        boolean res2 = trie.search("app");  // output: false
        System.out.println(res2);
        boolean res3 = trie.startsWith("app");  // output: true
        System.out.println(res3);
        trie.insert("app");
        boolean res4 = trie.search("app");  // output: true
        System.out.println(res4);
    }
}

/**
 * 解法二：字典树优化版（40ms）
 */
class Trie {
    Trie[] childs = null;
    int size = 26;
    boolean isEnd = false;

    /** Initialize your data structure here. */
    public Trie() {
        // 26 个子树，分别表示 26 个小写英文字母
        childs = new Trie[size];
    }

    /** Inserts a word into the trie. */
    public void insert(String word) {
        char[] arr = word.toCharArray();
        Trie cur = this;
        for (char c : arr) {
            if (cur.childs[c - 'a'] == null) {
                cur.childs[c - 'a'] = new Trie();
            }
            cur = cur.childs[c - 'a'];
        }
        cur.isEnd = true;
    }

    /** Returns if the word is in the trie. */
    public boolean search(String word) {
        char[] arr = word.toCharArray();
        Trie cur = this;
        for (char c : arr) {
            if (cur.childs[c - 'a'] == null) {
                return false;
            }
            cur = cur.childs[c - 'a'];
        }
        return cur.isEnd;
    }

    /** Returns if there is any word in the trie that starts with the given prefix. */
    public boolean startsWith(String prefix) {
        char[] arr = prefix.toCharArray();
        Trie cur = this;
        for (char c : arr) {
            if (cur.childs[c - 'a'] == null) {
                return false;
            }
            cur = cur.childs[c - 'a'];
        }
        return true;
    }
}

/**
 * 解法一：字典树（48ms）
 */
class Trie2 {
    private TrieNode root;

    /** Initialize your data structure here. */
    public Trie2() {
        root = new TrieNode();
    }

    /** Inserts a word into the trie. */
    public void insert(String word) {
        char[] arr = word.toCharArray();
        TrieNode node = root;
        for (int i = 0; i < arr.length; i++) {
            if (!node.containsKey(arr[i])) {
                // 不存在时，添加
                node.put(arr[i], new TrieNode());
            }
            node = node.get(arr[i]);
        }
        // 设置该节点，是一个结束节点，即从 root 根节点，到叶子节点 node，就是插入的 word 字符串
        node.setEnd();
    }

    /**
     * 查找字符串 word
     */
    public boolean search(String word) {
        // 查找字符串 word，与在字典树中查找以 word 为前缀的字符串，且以 d 为结束节点的字符串相同
        TrieNode node = searchPrefix(word);
        return node != null && node.isEnd();
    }

    /**
     * 查找前缀字符串
     */
    public TrieNode searchPrefix(String prefix) {
        char[] arr = prefix.toCharArray();
        TrieNode node = root;
        for (int i = 0; i < arr.length; i++) {
            if (node.containsKey(arr[i])) {
                node = node.get(arr[i]);
            } else {
                // 未找到
                return null;
            }
        }
        return node;
    }

    /**
     * 查找前缀字符串 prefix
     */
    public boolean startsWith(String prefix) {
        TrieNode node = searchPrefix(prefix);
        return node != null;
    }
}
